ההיררכיה של חומסקי
ההיררכיה של חומסקי, היא מיון משפחות של דקדוקים על פי כללי השכתוב שהם מתירים. ההיררכיה נקראת על שם נועם חומסקי, שהיה הראשון אשר ניסה למיין משפחות דקדוקים לפי כוחם היחסי.
ההיררכיה שחומסקי הציע מסווגת דקדוקים פורמליים לקבוצות שונות על פי כוח הבעה עולה. כלומר, כל קבוצה עוקבת יכולה ליצור מערך רחב יותר של שפות פורמליות מזו שקדמה לה. לטענת חומסקי, מודליזציה של הבטים מסוימים בשפה טבעית דורשת דקדוק פורמלי מורכב יותר (כפי שהוא נמדד בהיררכיית חומסקי) מאשר מודליזציה של שפות אחרות. לדוגמה, בזמן ששפה רגולרית חזקה מספיק לתאר מורפולוגיה אנגלית, היא אינה חזקה מספיק כדי לתאר תחביר אנגלי. בנוסף להיותה רלוונטית לבלשנות, יש להיררכיית חומסקי שימוש במדעי המחשב, ויש לה קשרים חשובים גם לתורת האוטומטים.
באופן כללי, כל משפחה מתקבלת על ידי הוספת אילוץ על כללי השכתוב של המשפחה הקודמת, ועל-כן יש יחס של הכלה בין קבוצות הדקדוקים.
כמו כן, כל משפחה מתאימה למשפחת אוטומטים מטיפוס מסוים. כלומר, יש שקילות בין קבוצת השפות שנוצרות על ידי דקדוקים ממשפחה מסוימת לבין קבוצות השפות המתקבלות על ידי אוטומטים מהמשפחה המתאימה.
חלוקה למשפחות
[עריכת קוד מקור | עריכה]המיון מתחלק ל-4 טיפוסי משפחות:
לקריאה נוספת
[עריכת קוד מקור | עריכה]- שמואל זקס ונסים פרנסיז, אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000, יחידה 6
